package alg;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

        public List<List<Integer>> fourSum(int[] nums, int target) {

            List<List<Integer>> ret = new ArrayList();
            //1.排序
            Arrays.sort(nums);
            //2.利用双指针解决问题
            int n = nums.length;
            for(int i = 0;i<n;){//固定数a
                //三数之和
                for(int j = i + 1 ;j < n;){//固定数b
                    //双指针
                    int left = j + 1,right = n - 1;
                    long aim = (long)target - nums[i] - nums[j];
                    while(left < right){
                        int sum = nums[left] + nums[right];
                        if(sum > aim){
                            right--;
                        }else if(sum < aim){
                            left++;
                        }else{
                            ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                            left++;
                            right--;
                            //去重
                            while(left < right && nums[left] == nums[left - 1]){
                                left++;
                            }
                            while(left < right && nums[right] == nums[right + 1]){
                                right--;
                            }
                        }
                    }
                    //去重2
                    j++;
                    while(j < n && nums[j] == nums[j - 1]){
                        j++;
                    }

                }
                //去重3
                i++;
                while(i < n && nums[i] == nums[i -1 ]){
                    i++;
                }
            }
            return ret;
        }

    public static void main(String[] args) {
        Solution alg1 = new Solution();
        int[] arrys = {-2,-1,0,0,1,2};
        List<List<Integer>> eas = alg1.fourSum(arrys,0);
        System.out.println(eas);

    }
    }



